package com.leet.code.lcof;

import java.util.LinkedList;

public class Code59_2 {
    public static void main(String[] args) {

    }


    static class MaxQueue {

        LinkedList<Integer> queue;
        LinkedList<Integer> maxQ;


        public MaxQueue() {
            queue = new LinkedList<>();
            maxQ = new LinkedList<>();
        }

        public int max_value() {
            if (maxQ.isEmpty()) {
                return -1;
            }
            return maxQ.getFirst();
        }

        public void push_back(int value) {
            while (!maxQ.isEmpty() && maxQ.getLast() < value) {
                maxQ.removeLast();
            }
            maxQ.add(value);
            queue.add(value);
        }

        public int pop_front() {
            if (queue.isEmpty()) {
                return -1;
            }
            if (maxQ.getFirst().equals(queue.getFirst())) {
                maxQ.removeFirst();
            }
            return queue.removeFirst();
        }
    }

}
